#include <stdio.h>
#include <stdlib.h>
#include "graph.h"
#include "queue.h"

int Init(Graph *graph)
{
     graph->MaxVertex = Default_Vertex_Size;
     graph->NumVertex = graph->NumEdge = 0;
     graph->NodeTable = malloc(sizeof(Vertex) * graph->MaxVertex);
     if (graph->NodeTable == NULL)
          return -1;
     for (int i = 0; i < graph->MaxVertex; i++)
          graph->NodeTable[i].adj = NULL;
     return 0;
}

int InsertVertex(Graph *graph, datatypeG data)
{
     if (graph->NumVertex == graph->MaxVertex)
          return -1;
     graph->NodeTable[graph->NumVertex++].data = data;
     return 0;
}

void Show(Graph *graph)
{
     Edge *p;
     for (int i = 0; i < graph->NumVertex; i++)
     {
          printf("%d %c:>", i, graph->NodeTable[i].data);
          p = graph->NodeTable[i].adj;
          while (p != NULL)
          {
               printf("%d--> ", p->dest);
               p = p->link;
          }
          printf("Nul.\n");
     }
}

int GetVertexPosion(Graph *graph, datatypeG vertex)
{
     for (int i = 0; i < graph->NumVertex; ++i)
     {
          if (graph->NodeTable[i].data == vertex)
               return i;
     }
     return -1;
}

int InsertEdge(Graph *graph, datatypeG vertex1, datatypeG vertex2)
{
     int p1 = GetVertexPosion(graph, vertex1);
     int p2 = GetVertexPosion(graph, vertex2);
     if (p1 == -1 || p2 == -1)
          return -1;
     //V1-->V2
     Edge *current = malloc(sizeof(Edge));
     if (current == NULL)
          return -2;
     current->dest = p2;
     current->link = graph->NodeTable[p1].adj;
     graph->NodeTable[p1].adj = current;
     //V2-->V1
     current = malloc(sizeof(Edge));
     if (current == NULL)
          return -3;
     current->dest = p1;
     current->link = graph->NodeTable[p2].adj;
     graph->NodeTable[p2].adj = current;
     ++graph->NumEdge;
     return 0;
}

int RemoveEdge(Graph *graph, datatypeG vertex1, datatypeG vertex2)
{
     int p1 = GetVertexPosion(graph, vertex1);
     int p2 = GetVertexPosion(graph, vertex2);
     if (p1 == -1 || p2 == -1)
          return -1;
     Edge *p = NULL, *q = NULL;
     //删除V1-->V2边
     p = graph->NodeTable[p1].adj;
     while (p != NULL && p->dest != p2)
     {
          q = p;
          p = p->link;
     }
     if (p == NULL)
          return -2;
     if (q == NULL) //p指向的第一个结点就是要找的结点,这时候q还为空
          graph->NodeTable[p1].adj = p->link;
     else
          q->link = p->link;
     free(p);
     //删除V2-->V1边
     p = graph->NodeTable[p2].adj;
     q = NULL;
     //V1-->V2有边，那么V2-->V1就一定有边,否则这个图的结构就是错误的,所以这里不需要p==NULL的判断
     while (p->dest != p1)
     {
          q = p;
          p = p->link;
     }
     if (q == NULL) //p指向的第一个结点就是要找的结点,这时候q还为空
          graph->NodeTable[p2].adj = p->link;
     else
          q->link = p->link;
     free(p);
     --graph->NumEdge;
     return 0;
}

int RemoveVertex(Graph *graph, datatypeG vertex)
{
     int p1 = GetVertexPosion(graph, vertex);
     if (p1 == -1)
          return -1;
     //删除与结点关联的边
     Edge *pre = NULL, *current, *next;
     current = graph->NodeTable[p1].adj;
     while (current != NULL)
     {
          int p2 = current->dest;
          next = graph->NodeTable[p2].adj;
          while (next->dest != p1)
          {
               pre = next;
               next = next->link;
          }
          if (pre == NULL)
               graph->NodeTable[p2].adj = next->link;
          else
               pre->link = next->link;
          free(next);
          graph->NodeTable[p1].adj = current->link;
          free(current);
          current = graph->NodeTable[p1].adj;
          --graph->NumEdge;
     }
     //删除结点
     --graph->NumVertex;
     graph->NodeTable[p1].data = graph->NodeTable[graph->NumVertex].data;
     graph->NodeTable[p1].adj = graph->NodeTable[graph->NumVertex].adj;
     current = graph->NodeTable[p1].adj;
     while (current != NULL)
     {
          int k = current->dest;
          next = graph->NodeTable[k].adj;
          while (next != NULL)
          {
               if (next->dest == graph->NumVertex)
               {
                    next->dest = p1;
                    break;
               }
               next = next->link;
          }
          current = current->link;
     }
     return 0;
}

void Destory(Graph *graph)
{
     Edge *p;
     for (int i = 0; i < graph->NumVertex; i++)
     {
          while ((p = graph->NodeTable[i].adj) != NULL)
          {
               graph->NodeTable[i].adj = p->link;
               free(p);
          }
     }
     free(graph->NodeTable);
     graph->NodeTable = NULL;
     graph->NumVertex = graph->NumEdge = 0;
}

int GetFirstNeighbor(Graph *graph, datatypeG vertex)
{
     int p = GetVertexPosion(graph, vertex);
     if (p == -1)
          return -1;
     Edge *current = graph->NodeTable[p].adj;
     if (current != NULL)
          return current->dest;
     return -2;
}

int GetNextNeighbor(Graph *graph, datatypeG vertex1, datatypeG vertex2)
{
     int p1 = GetVertexPosion(graph, vertex1);
     int p2 = GetVertexPosion(graph, vertex2);
     if (p1 == -1 || p2 == -1)
          return -1;
     Edge *current = graph->NodeTable[p1].adj;
     while (current != NULL && current->dest != p2)
          current = current->link;
     if (current != NULL && current->link != NULL)
          return current->link->dest;
     return -2;
}

datatypeG GetVertexValue(Graph *graph, int p)
{
          return graph->NodeTable[p].data;
}

//============================================================================
int DFS(Graph *graph, datatypeG vertex)
{
     int p = GetVertexPosion(graph, vertex);
     if (p == -1)
          return -1;
     int *visited = malloc(sizeof(int) * graph->NumVertex);
     if (visited == NULL)
          return -2;
     for (int i = 0; i < graph->NumVertex; i++)
          visited[i] = 0;

     DFS_(graph, p, visited);

     free(visited);
     printf("Nul.");
     return 0;
}

void DFS_(Graph *graph, int p, int visited[])
{
     datatypeG v = GetVertexValue(graph, p);
     printf("%c-->", v);     //访问该结点
     visited[p] = 1;
     int w = GetFirstNeighbor(graph, v);
     while (w != -2) //返回-2表示已经到达链表尽头
     {
          if (!visited[w])
               DFS_(graph, w, visited);
          w = GetNextNeighbor(graph, v, GetVertexValue(graph, w));
     }
}

int BFS(Graph *graph, datatypeG vertex)
{
     int p = GetVertexPosion(graph, vertex);
     if (p == -1)
          return -1;
     int n = graph->NumVertex;
     int *visited = malloc(sizeof(int) * n);
     if (visited == NULL)
          return -2;
     for (int i = 0; i < n; i++)
          visited[i] = 0;

     Queue queue;
     InitQueue(&queue);
     printf("%c-->", GetVertexValue(graph, p));  //把头访问完后将其入队
     visited[p] = 1;
     EnQueue(&queue, p);

     while (!EmptyQueue(&queue))
     {
          GetHead(&queue, &p);
          DeQueue(&queue);
          int w = GetFirstNeighbor(graph, GetVertexValue(graph, p));
          while (w != -1)
          {
               if (!visited[w])
               {
                    printf("%c-->", GetVertexValue(graph, w));
                    visited[w] = 1;
                    EnQueue(&queue, w);
               }
               w = GetNextNeighbor(graph, GetVertexValue(graph, p), GetVertexValue(graph, w));
          }
     }
     printf("Nul.");
     free(visited);

     return 0;
}

int Connection(Graph *graph)
{
     int n = graph->NumVertex;
     int *visited = malloc(sizeof(int) * n);
     if (visited == NULL)
          return -1;
     for (int i = 0; i < n; i++)
          visited[i] = 0;

     for (int i = 0; i < n; i++)
     {
          if (!visited[i])
               DFS_(graph, i, visited);
     }

     printf("Nul.\n");
     free(visited);

     return 0;
}
